Today’s Agenda

  • Hausdorff Distance
  • Gromov–Hausdorff Distance
  • Hasudorff vs Gromov–Hausdorff
  • The curious case of the circle
  • Lower bounds
    • Riemannian manifolds
    • metric graphs
  • Future work

Definition 1 (Directed Hausdorff Distance) For two subsets compact \(X,Y\subset\mathbb R^n\), their directed Hausdorff distance is \[ \vec{d}_H(X,Y)=\inf\big\{r\geq0\mid X\subset \bigcup_{y\in Y} B(y,r)\big\}. \]

All metric properties but symmetry.

Definition 2 (Hausdorff Distance)  

\[\begin{aligned} d_H(X,Y) &=\max\big\{\vec{d}_H(X,Y),\vec{d}_H(Y,X)\big\} \\ &=\sup\big\{r\geq0 \mid X\subset \bigcup_{y\in Y} B(y,r)\text{ and }Y\subset \bigcup_{x\in X} B(x,r)\big\}. \end{aligned}\]

Why Only Euclidean Subsets?

Definition 3 (Hausdorff Distance) Let \((Z,d)\) be a metric space and \(X, Y\subset Z\) compact subsets. \[ d^Z_H(X,Y)=\sup\big\{r\geq0 \mid X\subset \bigcup_{y\in Y} B(y,r)\text{ and }Y\subset \bigcup_{x\in X} B(x,r)\big\}. \]

\(d_H(X, Y)=0\) if and only if \(X=Y\).

\(Z=S^1\) is the circle with circumference \(2\pi\)

\[ d_H(X,S^1)=\frac{\pi}{4}. \]

What if the subsets \(X,Y\) have no common embeddding?

Isometric embedding

Definition 4 (The Gromov–Hausdorff Distance) For two abstract metric spaces \((X,d_X)\) and \((Y,d_Y)\), define \[ d_{GH}(X,Y)=\inf d^Z_H(f(X),g(Y)) \]

An Example

Some Properties and Results

  • \(d_{GH}(X,Y)=0\) if and only if \(X\), \(Y\) are isometric

  • \[\tfrac{1}{2}|diam(X)-diam(Y)|\leq d_{GH}(X,Y)\leq \tfrac{1}{2}\max\big\{diam(X), diam(Y)\big\}\]

  • When \(X, Y\) are finite metric spaces

    • Computationally feasible (distortion definition)
    • Minimization problem with exponential search space

  • If \(X,Y\) metric trees, then \(NP\)-hard (Aggarwal et al.)

  • If \(X,Y\subset\mathbb{R}^1\), then \(\frac{5}{4}\)-approximable (Majhi et al.)

  1. Let \((Z,d)\) be a metric space and \(X,Y\subset Z\)
    • \(d^Z_H(X,Y)\) is well-defined
  2. \((X,d)\) and \((Y,d)\) are also metric spaces
    • \(d_{GH}(X,Y)\) can also be defined

How the two distances \(d^Z_H(X,Z)\) and \(d_{GH}(X,Y)\) compare?

  • \(d_{GH}(X,Y)\color{green}{\leq} d_H(X,Y)\)
    • \(Z\) is just one ambient of \(X,Y\)!
  • \(d_{GH}(X,Y) \color{red}{=} d_H(X,Y)\)?

The Circle and A Subset

  • Let \(Z\) be the circle with circumference \(2\pi\)
  • \(X\) be a singleton subset, \(Y=Z\)
  • \(\color{green}{d_H(X,S^1)}=\color{red}{d_{GH}(X,S^1)}=\frac{\pi}{2}\)
  • \(\frac{1}{2}\pi\leq d_{GH}(X,S^1)\leq \frac{1}{2}\pi \implies d_{GH}(X,S^1)=\frac{\pi}{2}\)

The Circle and A Subset

  • \(\color{green}{d_H(X,S^1)}=\frac{\pi}{4}\)
  • \(\frac{1}{2}0\leq \color{red}{d_{GH}(X,S^1)}\leq \frac{1}{2}\pi \implies ?\)
  • One can show that \(d_{GH}(X,S^1)=d_H(X,S^1)\)

The Curious Case of the Circle

\[ \frac{\pi}{3}=\color{red}{d_{GH}(X,S^1)}<\color{green}{d_{H}(X,S^1)}=\frac{\pi}{3}+\varepsilon. \]

Density is The Key

Theorem 1 (DCG 2023) For \(X\subset S^1\) with \(d_H(X,S^1)<\color{red}{\frac{\pi}{6}}\), then \(d_{GH}(X,S^1)=d_H(X,S^1)\).

  • Proof is topological (Vietoris–Rips complex, Nerve Lemma)
  • Is \(\frac{\pi}{6}\) optimal?

Theorem 2 (2024) For \(X\subset S^1\) with \(d_H(X,S^1)<\color{green}{\frac{\pi}{3}}\), then \(d_{GH}(X,S^1)=d_H(X,S^1)\).

  • Proof is purely geometric

Another Perspective: Lower Bound

  • \(d_{GH}(X,S^1)\geq\min\big\{d_H(X, S^1),\frac{\pi}{3}\big\}\).

Corollary 1 (Two Subsets) For \(X,Y\subset S^1\) with \(d_H(Y,S^1)\leq\varepsilon\), then \[d_{GH}(X,Y)\geq\min\big\{d_H(X, Y)-2\varepsilon,\tfrac{\pi}{3}-\varepsilon\big\}.\]

  • \(O(n^2)\) lower-bound for \(\max{|X|, |Y|}=n\).

Non-Trivial Lower Bounds

  • Intuition: when a sample becomes dense enough, it starts to capture the geometry of the space.

  • Generally: \(d_{GH}(X,Z)\geq\min\big\{\color{red}{C}\cdot d_H(X, Z), \color{red}{D}\big\}\)?

    • Cirlce: \(C=1\) and \(D=\frac{\pi}{3}\).

Theorem 3 (Bad News) For any \(C>0\), there exists a compact metric space \(Z\) and a subset \(X\subseteq Z\) with \(d_{GH}(X,Z) < C \cdot d_{H}(X,Z).\)

Good News

Theorem 4 (Closed Riemannian Manifolds) For \(X\subset M\), we have \[ d_{GH}(X,M)\geq\min\bigg\{\color{green}{\frac{1}{2}}d_H(X, S^1),\color{green}{\frac{\rho}{6}}\bigg\}. \]

  • \(\rho\) is the convexity radius of \(M\)
  • \(C=\frac{1}{2}\) can be improved using Jung’s theorem

Metric Trees and Graphs

Theorem 5 (Trees) Let \(T\) be a compact tree with finite edges. For any \(X\subset T\) so that \(d_H(T,X)<\vec{d}_H(\delta T, X)\), we have \[ d_{GH}(X,T)=d_H(X, T). \]

Theorem 6 (Graphs) Let \(G\) be a compact tree with finite edges. For any \(X\subset G\) so that \(d_H(G,X)<\vec{d}_H(\delta G, X)\), we have \[ d_{GH}(X,G)\geq\min\bigg\{{d_H(X, S^1),\tfrac{e(G)}{12}}\bigg\}. \]

  • \(e(G)\) denotes the length of the shortest edge.

Questions

  • For metric graphs, is the density constant \(\frac{e(G)}{12}\) optimal?

    • We conjecture that \(\frac{e(G)}{8}\) should suffice.

  • What about Riemannian manifolds with bounday?

  • Are there classes of metric spaces—like the circle, metric graphs—so that \(C=1\)?

Thank you